A Virtual Private Network (VPN) provides secure connectivity among distributed customer sites. VPNs can be implemented by using Border Gateway (BGP) and MPLS (Multiprotocol Label Switching) technologies. The official document on this topic is RFC 2547, BGP/MPLS VPNs, by Rosen and Rekhter at http://www.ietf.org and is incorporated by reference. MPLS and VPN Architectures, by Pepelnjak and Guichard, Cisco Press 2001 is also a valuable source of information and is also incorporated by reference. It provides a practical guide to understanding, designing, and deploying MPLS and MPLS-enabled VPNs.
A backbone network connects a plurality of customer sites that comprise a plurality of VPNs. Each site has one or more customer edge (CE) routers that connect to one or more provider edge (PE) routers in the backbone network. The PE routers in the backbone may be directly connected. Alternatively, the PE routers may be connected via provider (P) routers. The PE and P routers are located in service nodes that are geographically distributed.
Capacity planning and traffic engineering for backbone networks is required to provide adequate quality-of-service. A variety of software tools in the current art can be used for this purpose. One vendor that provides such tools is the Wide Area Network Design Laboratory. A description of their products is available at http://www.wandl.com. A second vendor is Optimum Network Performance. See http://www.opnet.com for more information about their products. Other vendors also offer products in this area.
These products require input that describes the traffic demands on a backbone network. This data can be provided as a matrix that shows the number of bytes and packets transmitted between PE routers. It is necessary to report this data separately for each type-of-service. A traffic matrix is a three dimensional matrix T[x][y][z] where x is the index of an ingress PE router, y is the index of an egress PE router, and z is the type-of-service (TOS). The values of x and y range from 0 to the number of PE routers−1. The value of z ranges from 0 to the number of types of service−1.
Alternatively, a capacity planning or traffic engineering tool may require a traffic matrix that characterizes the number of bytes and packets transmitted between service nodes. A traffic matrix is a three dimensional matrix T[x][y][z] where x is the index of an ingress service node, y is the index of an egress service node, and z is the type-of-service (TOS). The values of x and y range from 0 to the number of service nodes−1. The value of z ranges from 0 to the number of types of service−1.
A variety of protocols are used to route packets in the backbone network. These protocols are defined in specifications at http://www.ietf.org. For example, the Open Shortest Path First (OSPF) protocol is used to route within an autonomous system as described in RFC 2328, OSPF Version 2, by J. Moy. The Border Gateway Protocol is used to route among autonomous systems as described in RFC 1771, A Border Gateway Protocol, by Y. Rekhter and T. Li. The Border Gateway Protocol is also described in RFC 1772, Application of the Border Gateway Protocol in the Internet, by Y. Rekhter and P. Gross. The Multi-Protocol Label Switching (MPLS) technology is described in RFC 3031 Multiprotocol Label Switching Architecture by Rosen, et. al. Many books describe these protocols as well. For example, Computer Networks, Third Edition, by A. Tanenbaum, Prentice-Hall, 1996 is an excellent reference text. Routing in the Internet, by Christian Huitema, Prentice Hall, 1995 is also valuable. BGP4 Inter-Domain Routing in the Internet, by John Stewart III, Addison-Wesley, 1999 describes BGP-4. See MPLS: Technology and Applications, by Davie and Rekhter, Morgan Kafmann, 2000 for a discussion of that protocol.
PE routers in the current art can be configured to generate records that provide summary information about packet flows. A flow is a sequence of packets from a source to a destination. A PE router identifies a flow by examining the packets that enter its interfaces. Packets having identical values for source address/port, destination address/port, protocol, type-of-service, and input interface address are considered to be part of the same flow.
Flow records contain multiple items (e.g. source address/port, destination address/port, protocol, type-of-service, input interface address). In addition, a PE router counts the number of bytes and packets that comprise this flow and includes these values in the flow record. Flow records provide raw data about packet flows through a network. A PE router is configured to transmit flow records to a specific address and port. This occurs when the flow completes. It may also occur multiple times during a flow.
Cisco is a network equipment vendor that provides flow record generation. This feature on their products is called NetFlow. Each Version 5 NetFlow record contains source IP address, destination IP address, source TCP or UDP port, destination TCP or UDP port, next hop router IP address, incoming interface address or index, outgoing interface address or index, packet count, byte count, start of flow timestamp, end of flow timestamp, IP protocol, type-of-service, TCP flags, source autonomous system, destination autonomous system, source subnet, and destination subnet. Other formats are also available. See http://www.cisco.com for a detailed description of this feature.
It is a difficult task to generate traffic matrixes. Traffic volumes through a backbone network are substantial. Flow records may total several megabytes. Centralized architectures that upload these records to one machine for processing are not satisfactory. The time to upload and process the records is substantial.
Therefore, a need exists for a distributed architecture in which records may be processed in each service node. This will significantly reduce the time to generate a matrix. It will also allow matrixes to be generated more frequently. More frequent generation of matrixes provides a more accurate view of the backbone network traffic.